#include <bits/stdc++.h>

using namespace std;

// 模拟， 移动
class Solution {
public:
    int countValidSelections(vector<int>& nums) {
        int total=reduce(nums.begin(), nums.end());
        int ans=0, pre=0;
        for(int x: nums){
            if(x) pre+=x;
            else if(pre*2==total) ans+=2;
            else if(abs(pre*2-total)==1) ans++;
        }
        return ans;
    }
};

class Solution2{
public:
    bool isZeroArr(vector<int>& nums, vector<vector<int>>& queries){
        int n=nums.size(); vector<int> d(n+1);
        for(auto &qry: queries){
            d[qry[0]]++;
            d[qry[1]+1]--;
        }
        for(int i=0,now=0;i<n;i++){
            now+=d[i];
            if(now<nums[i]) return false;
        }
        return true;
    }
};

class Solution3{
public:
    int minZeroArr(vector<int>& nums, vector<vector<int>>& queries){
        int n = nums.size();
        vector<int> diff(n + 1);
        auto check = [&](int k) -> bool {
//            ranges::fill(diff, 0);
            fill(diff.begin(), diff.end(),0);
            for (int i = 0; i < k; i++) { // 前 k 个询问
                auto& q = queries[i];
                int l = q[0], r = q[1], val = q[2];
                diff[l] += val;
                diff[r + 1] -= val;
            }

            int sum_d = 0;
            for (int i = 0; i < n; i++) {
                sum_d += diff[i];
                if (nums[i] > sum_d) {
                    return false;
                }
            }
            return true;
        };

        int q = queries.size();
        int left = -1, right = q + 1;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            (check(mid) ? right : left) = mid;
        }
        return right <= q ? right : -1;
    }
};

//
class Solution4 {
public:
    int minDifference(vector<int>& nums) {
        int n=nums.size();
        int min_l=INT_MAX, max_r=0;
        for(int i=0;i<n;i++){
            if(nums[i]!=-1&&(i>0&&nums[i-1]==-1 || i<n-1 && nums[i+1]==-1)){
                min_l=min(min_l,nums[i]);
                max_r=max(max_r, nums[i]);
            }
        }
        int ans=0;
        auto update_ans=[&](int l, int r, bool big){
            int d=(min(r-min_l, max_r-l)+1)/2;
            if(big) d=min(d,(max_r-min_l+2)/3);
            ans=max(ans, d);
        };
        int pre_i=-1;
        for(int i=0;i<n;i++){
            if(nums[i]==-1) continue;
            if(pre_i>=0) {
                if (i - pre_i == 1)
                    ans = max(ans, abs(nums[i] - nums[pre_i]));
                else {
                    update_ans(min(nums[pre_i], nums[i]), max(nums[pre_i],nums[i]),i-pre_i>2);
                }
            } else if(i>0){
                update_ans(nums[i], nums[i], false);
            }
            pre_i=i;
        }
        if(0<=pre_i && pre_i<n-1){
            update_ans(nums[pre_i], nums[pre_i], false);
        }
        return ans;
    }
};

int main(){
    vector<int> nums={1,0,2,0,3};
    Solution s; cout<<s.countValidSelections(nums)<<endl;
    vector<int> nums2={1,0,1}; vector<vector<int>> queries={{0,2}};
    Solution2 s2; cout<<s2.isZeroArr(nums2, queries)<<endl;
    vector nums3={2,0,2}; vector<vector<int>> queries3={{0,2,1},{0,2,1},{1,1,3}};
    Solution3 s3; cout<<s3.minZeroArr(nums3, queries3)<<endl;
    vector<int> nums4={-1,10,-1,8};
    Solution4 s4; cout<<s4.minDifference(nums4)<<endl;
}